{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge k Sorted Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #divide-and-conquer #heap-priority-queue #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #分治 #堆（优先队列） #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mergeKLists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并 K 个升序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表数组，每个链表都已经按升序排列。</p>\n",
    "\n",
    "<p>请你将所有链表合并到一个升序链表中，返回合并后的链表。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>lists = [[1,4,5],[1,3,4],[2,6]]\n",
    "<strong>输出：</strong>[1,1,2,3,4,4,5,6]\n",
    "<strong>解释：</strong>链表数组如下：\n",
    "[\n",
    "  1-&gt;4-&gt;5,\n",
    "  1-&gt;3-&gt;4,\n",
    "  2-&gt;6\n",
    "]\n",
    "将它们合并到一个有序链表中得到。\n",
    "1-&gt;1-&gt;2-&gt;3-&gt;4-&gt;4-&gt;5-&gt;6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>lists = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>lists = [[]]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>k == lists.length</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10^4</code></li>\n",
    "\t<li><code>0 &lt;= lists[i].length &lt;= 500</code></li>\n",
    "\t<li><code>-10^4 &lt;= lists[i][j] &lt;= 10^4</code></li>\n",
    "\t<li><code>lists[i]</code> 按 <strong>升序</strong> 排列</li>\n",
    "\t<li><code>lists[i].length</code> 的总和不超过 <code>10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-k-sorted-lists](https://leetcode.cn/problems/merge-k-sorted-lists/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-k-sorted-lists](https://leetcode.cn/problems/merge-k-sorted-lists/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4,5],[1,3,4],[2,6]]', '[]', '[[]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return ListNode().next\n",
    "        \n",
    "        items = []\n",
    "        for _list in lists:\n",
    "            while _list:\n",
    "                items.append(_list.val)\n",
    "                _list = _list.next\n",
    "                \n",
    "            \n",
    "        items = sorted(items)\n",
    "        \n",
    "        \n",
    "        result = temp = ListNode()\n",
    "        \n",
    "        for item in items:\n",
    "            temp.next = ListNode(item)\n",
    "            temp = temp.next\n",
    "        \n",
    "        return result.next\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        final_rel=[]\n",
    "        now_list=[]\n",
    "        flag=1\n",
    "        l_len=len(lists)\n",
    "        min_index=0\n",
    "        while(flag):\n",
    "            min=10000000\n",
    "            flag=0\n",
    "            for index in range(l_len):\n",
    "                if(lists[index]!=None):\n",
    "                    flag=1\n",
    "                    if(min<lists[index].val):\n",
    "                        continue\n",
    "                    else:\n",
    "                        min=lists[index].val\n",
    "                        min_index=index\n",
    "            if(flag):\n",
    "                final_rel.append(min)\n",
    "                lists[min_index]=lists[min_index].next\n",
    "        return final_rel"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        lens = len(lists)\n",
    "        if not lens:\n",
    "            return []\n",
    "        elif lens == 1:\n",
    "            return lists[0]\n",
    "        else:\n",
    "            return self.devide(lists, 0, lens - 1)\n",
    "\n",
    "    def devide(self, lists, l_p, r_p):\n",
    "        if l_p == r_p:\n",
    "            return lists[l_p]\n",
    "        else:\n",
    "            mid = (l_p + r_p) // 2\n",
    "            left = self.devide(lists, l_p, mid)\n",
    "            right = self.devide(lists, mid + 1, r_p)\n",
    "            return self.merge2Lists(left, right)\n",
    "\n",
    "    def merge2Lists(self, list1, list2):\n",
    "        root = ListNode(0)\n",
    "        tmp = root\n",
    "        while list1 and list2:\n",
    "            if list1.val > list2.val:\n",
    "                tmp.next = list2\n",
    "                list2 = list2.next\n",
    "                tmp = tmp.next\n",
    "            else:\n",
    "                tmp.next = list1\n",
    "                list1 = list1.next\n",
    "                tmp = tmp.next\n",
    "        if list1:\n",
    "            tmp.next = list1\n",
    "        if list2:\n",
    "            tmp.next = list2\n",
    "        return root.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: 'List[ListNode]') -> 'ListNode':\n",
    "        from heapq import heappush, heappop, heapreplace, heapify\n",
    "        dummy = node = ListNode(0)\n",
    "        h = [(n.val, i, n) for i, n in enumerate(lists) if n]\n",
    "        # To make sure this runs in Python3, simply add a tie-breaker in your heap elements (tuples). This assures that the heapq algo will never compare two variables of type ListNode.\n",
    "        heapify(h)\n",
    "        while h:\n",
    "            v, i, n = h[0]\n",
    "            if n.next is None:\n",
    "                heappop(h)\n",
    "            else:\n",
    "                heapreplace(h, (n.next.val, i, n.next))\n",
    "            node.next = n\n",
    "            node = node.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        for i in range(len(lists)):\n",
    "            item = lists[i]\n",
    "            while item != None:\n",
    "                res.append(item.val)\n",
    "                item = item.next\n",
    "        res = sorted(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    import heapq\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        ret,heap=[],[]\n",
    "        \n",
    "        for lst in lists:\n",
    "            while lst:\n",
    "            \n",
    "                heapq.heappush(heap,lst.val)\n",
    "\n",
    "                lst=lst.next\n",
    "            \n",
    "        while heap:\n",
    "            ret.append(heapq.heappop(heap))\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        a=[]\n",
    "        for i in range(len(lists)):\n",
    "            # b=lists[i]\n",
    "            while lists[i]:\n",
    "                a.append(lists[i].val)\n",
    "                lists[i]=lists[i].next\n",
    "        a.sort()\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        nodes = []\n",
    "        cur = head = ListNode(0)\n",
    "        for l in lists:\n",
    "            \n",
    "            while l:\n",
    "                nodes.append(l.val)\n",
    "                l = l.next\n",
    "        for x in sorted(nodes):\n",
    "            cur.next = ListNode(x)\n",
    "            cur = cur.next\n",
    "        \n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        elems = []\n",
    "        for p in lists:\n",
    "            while p:\n",
    "                elems.append(p.val)\n",
    "                p = p.next\n",
    "        elems.sort()\n",
    "        \n",
    "        dummy = helper = ListNode(0)\n",
    "        for elem in elems:\n",
    "            helper.next = ListNode(elem)\n",
    "            helper = helper.next\n",
    "        \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        lists = list(filter(lambda ll: ll is not None, lists))\n",
    "        if lists is None or len(lists) == 0:\n",
    "            return None\n",
    "        result_head = ListNode(-1)\n",
    "        pointers = [head for head in lists]\n",
    "        min_value = pointers[0].val\n",
    "        main_pointer = result_head\n",
    "        min_index = 0\n",
    "        len_pointer = len(pointers)\n",
    "        while min_value is not None:\n",
    "            for i in range(len_pointer):\n",
    "                pointer = pointers[i]\n",
    "                if pointer is None:\n",
    "                    continue\n",
    "                if pointer.val <= min_value:\n",
    "                    min_value = pointer.val\n",
    "                    min_index = i\n",
    "            main_pointer.next = ListNode(min_value)\n",
    "            main_pointer = main_pointer.next\n",
    "            pointers[min_index] = pointers[min_index].next\n",
    "            min_value = None\n",
    "            for i in range(len_pointer):\n",
    "                pointer = pointers[i]\n",
    "                if pointer is not None:\n",
    "                    min_value = pointer.val\n",
    "                    break\n",
    "        return result_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists):\n",
    "        head = p = ListNode(0)\n",
    "        n = 1\n",
    "        q = PriorityQueue()\n",
    "\n",
    "        for l in lists:\n",
    "            if l:\n",
    "                q.put((l.val, n, l))\n",
    "                n += 1 \n",
    "\n",
    "        while not q.empty():\n",
    "            val, m, node = q.get()\n",
    "            p.next = ListNode(val)\n",
    "            p = p.next\n",
    "            node = node.next #关键\n",
    "            if node:\n",
    "                q.put((node.val, n, node))\n",
    "                n += 1\n",
    "        \n",
    "        return head.next\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "    mn*log(m)  m是链表上限个数　n是长度上限\n",
    "    假设m条长度为n的做合并，m路归并问题　最快的办法是两两归并\n",
    "    第一轮: m/2组 归并过程将两个链表分别遍历一次　2n　　　　　　第一轮:m*n\n",
    "    第二轮: m/4组*4n=mn\n",
    "    ...\n",
    "    总共log(m)轮　　故时间复杂度为mn*log(m)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: 'List[ListNode]') -> 'ListNode':\n",
    "        m = len(lists)\n",
    "        if(m==1):\n",
    "            return lists[0]\n",
    "        if(m==0):\n",
    "            return None\n",
    "        print ('链表个数为',m)\n",
    "        for i in range(m//2):\n",
    "            pre = lists[2*i] #插入位置\n",
    "            b = lists[2*i+1]\n",
    "            if(pre==None):\n",
    "                lists[2*i]=b\n",
    "                continue\n",
    "            \n",
    "            if(b==None):\n",
    "                continue\n",
    "            # 如果第二个链首元素小于第一个　则更换链首\n",
    "            if(b.val<pre.val):\n",
    "                c = b.next\n",
    "                b.next = pre\n",
    "                lists[2*i] = b\n",
    "                b = c\n",
    "            pre = lists[2*i]    \n",
    "            a = pre.next  #当前被比较值\n",
    "            \n",
    "            while (b!=None):               \n",
    "                while(a!=None and b.val>a.val):\n",
    "                    pre = a\n",
    "                    a = a.next\n",
    "                if(a==None):\n",
    "                    pre.next = b\n",
    "                    break\n",
    "                #找到插入位置\n",
    "                pre.next = b\n",
    "                c = b.next\n",
    "                if(c==None):\n",
    "                    d = b\n",
    "                b.next = a\n",
    "                pre = b\n",
    "                b = c\n",
    "                #print(pre.val,a.val,b.val)\n",
    "\n",
    "            pre = lists[2*i]\n",
    "            while(pre!=None):\n",
    "                print(pre.val,end='')\n",
    "                pre=pre.next\n",
    "            #print()\n",
    "        print ('    链表个数为',len(lists))\n",
    "        for i in range(m//2):\n",
    "            lists.remove(lists[2*i+1-i])\n",
    "            print('移除',2*i+1)\n",
    "\n",
    "        \n",
    "        return self.mergeKLists(lists)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        res = None\n",
    "        if not lists:\n",
    "            return res\n",
    "        d={}\n",
    "        reslist = []\n",
    "        for i in range(len(lists)):\n",
    "            d[i]=[]\n",
    "            node = lists[i]\n",
    "            while node:\n",
    "                d[i].append(node.val)\n",
    "                node = node.next\n",
    "            reslist += d[i]\n",
    "            reslist.sort()\n",
    "        if not reslist:\n",
    "            return res\n",
    "        else:\n",
    "            \n",
    "            for n in reslist:\n",
    "                if not res:\n",
    "                    res = ListNode(n)\n",
    "                    upnode = res\n",
    "                else:\n",
    "                    node = ListNode(n)\n",
    "                    upnode.next = node\n",
    "                    upnode = upnode.next\n",
    "            return res\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution(object):\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        tmp=[]\n",
    "        for i in lists:\n",
    "            if i not in tmp and i!=None:\n",
    "                tmp.append(i)\n",
    "        if not tmp:\n",
    "            return\n",
    "        ans=ListNode(None)\n",
    "            \n",
    "        p=ans\n",
    "        listval=[]\n",
    "        listnum=[]\n",
    "        lists=tmp\n",
    "        for i in range(len(lists)):\n",
    "            listval.append(lists[i].val)\n",
    "            listnum.append(i)\n",
    "        Z=zip(listval,listnum)\n",
    "        Z=sorted(Z)\n",
    "        listval,listnum=zip(*Z)\n",
    "        listval,listnum=list(listval),list(listnum)\n",
    "        while listval:\n",
    "            p.next=ListNode(listval[0])\n",
    "            p=p.next\n",
    "            if lists[listnum[0]].next:\n",
    "                tmp=lists[listnum[0]].next.val\n",
    "                lists[listnum[0]]=lists[listnum[0]].next\n",
    "                num=listnum[0]\n",
    "                del listval[0]\n",
    "                del listnum[0]\n",
    "                if listval:\n",
    "                    if tmp<=listval[0]:\n",
    "                        listval.insert(0,tmp)\n",
    "                        listnum.insert(0,num)\n",
    "                    elif tmp>=listval[-1]:\n",
    "                        listval.append(tmp)\n",
    "                        listnum.append(num)\n",
    "                    else:\n",
    "                        for i in range(len(listval)):\n",
    "                            if listval[i]>=tmp:\n",
    "                                break\n",
    "                        listval.insert(i,tmp)\n",
    "                        listnum.insert(i,num)\n",
    "                else:\n",
    "                    listval.append(tmp)\n",
    "                    listnum.append(num)\n",
    "                    \n",
    "            else:\n",
    "                del listval[0]\n",
    "                del listnum[0]\n",
    "        return ans.next\n",
    "            \n",
    "        \n",
    "            \n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Node:\n",
    "    def __init__(self, node):\n",
    "        self.val = node.val\n",
    "        self.next = None\n",
    "        \n",
    "    def __lt__(self, a):\n",
    "        return self.val < a.val\n",
    "\n",
    "def node(head):\n",
    "    if head is None:\n",
    "        return None\n",
    "    else:\n",
    "        nhead = Node(head)\n",
    "        nhead.next = node(head.next)\n",
    "        return nhead\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        lists = [i for i in lists if i is not None]\n",
    "        if len(lists) == 0:\n",
    "            return None\n",
    "        ans = ListNode(0)\n",
    "        p = ans\n",
    "        lists = [node(i) for i in lists]\n",
    "        heap = [i for i in lists]\n",
    "        import heapq\n",
    "        heapq.heapify(heap)\n",
    "        while len(heap) > 0:\n",
    "            n = heapq.heappop(heap)\n",
    "            p.next = ListNode(n.val)\n",
    "            p = p.next\n",
    "            if n.next is not None:\n",
    "                heapq.heappush(heap, n.next)\n",
    "        return ans.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if len(lists) == 0:\n",
    "            return None\n",
    "        if len(lists) == 1:\n",
    "            return lists[0]\n",
    "        # num = 0\n",
    "        # for item in lists:\n",
    "        #     if item is None:\n",
    "        #         num += 1\n",
    "        # if num == len(lists):\n",
    "        #     return None\n",
    "        result = lists[0]\n",
    "        for i in range(len(lists)):\n",
    "            if i > 0:\n",
    "                result = self.merge2lists(result, lists[i])\n",
    "        return result\n",
    "\n",
    "    def merge2lists(self, l1: list, l2: list) -> ListNode:\n",
    "        head = ListNode(0)\n",
    "        start = head\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                start.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                start.next = l2\n",
    "                l2 = l2.next\n",
    "            start = start.next\n",
    "        if l1:\n",
    "            start.next = l1\n",
    "        if l2:\n",
    "            start.next = l2\n",
    "        if start.next is None:\n",
    "            return None\n",
    "        return head.next\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "import heapq\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        #lists[i].val打印的是lists中第i个list的第一个节点的值\n",
    "        l,size=[],len(lists)\n",
    "        for i in range(size):\n",
    "            if lists[i]:\n",
    "                heapq.heappush(l,(lists[i].val,i))\n",
    "        dummy=ListNode(0)\n",
    "        cur=dummy\n",
    "        while l:\n",
    "            _,index=heapq.heappop(l)\n",
    "            head=lists[index]\n",
    "            cur.next=head\n",
    "            cur=cur.next\n",
    "            if head.next:\n",
    "                heapq.heappush(l,(head.next.val,index))\n",
    "                lists[index]=head.next\n",
    "                head.next=None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return\n",
    "        if len(lists)==1:\n",
    "            return lists[0]\n",
    "\n",
    "        def mergeTwoLists(l1, l2):\n",
    "            if not l1 and not l2:\n",
    "                return \n",
    "            if not l1:\n",
    "                return l2\n",
    "            if not l2:\n",
    "                return l1\n",
    "            cur1=l1\n",
    "            cur2=l2\n",
    "            helpcur=ListNode(1)\n",
    "            start=helpcur\n",
    "            while cur1 and cur2:\n",
    "                if cur1.val<=cur2.val:\n",
    "                    helpcur.next=cur1\n",
    "                    cur1=cur1.next\n",
    "                else:\n",
    "                    helpcur.next=cur2\n",
    "                    cur2=cur2.next\n",
    "                helpcur=helpcur.next\n",
    "            if cur1:\n",
    "                helpcur.next=cur1\n",
    "            elif cur2:\n",
    "                helpcur.next=cur2\n",
    "            return start.next\n",
    "        i=1\n",
    "        cur=lists[i-1]\n",
    "        while i<len(lists):\n",
    "            cur=mergeTwoLists(cur,lists[i])\n",
    "            i+=1\n",
    "        return cur\n",
    "       \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        ans = cur = ListNode()\n",
    "        heap = []\n",
    "        heapq.heapify(heap)\n",
    "        for i in range(len(lists)):\n",
    "            if lists[i]:\n",
    "                heapq.heappush(heap, (lists[i].val, i))\n",
    "                lists[i] = lists[i].next\n",
    "        \n",
    "        while heap:\n",
    "            val, idx = heapq.heappop(heap)\n",
    "            node = ListNode(val)\n",
    "            cur.next = node\n",
    "            cur = cur.next\n",
    "            if lists[idx] != None:\n",
    "                heapq.heappush(heap, (lists[idx].val, idx))\n",
    "                lists[idx] = lists[idx].next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        if len(lists) == 0:\n",
    "            return None\n",
    "        if len(lists) == 1 and lists[0]:\n",
    "            return lists[0]\n",
    "        # l1 = lists[:len(lists)//2]\n",
    "        # l2 = lists[len(lists)//2:]\n",
    "        # print(l1,l2)\n",
    "        # res = self.func(l1,l2)\n",
    "        \n",
    "        # for link in lists:\n",
    "        #     if link is None:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         res = self.merge(res, link)\n",
    "        return self.func(lists)\n",
    "    \n",
    "    def func(self, lists):\n",
    "        res = None\n",
    "        if len(lists) < 4:\n",
    "            for link in lists:\n",
    "                if link is None:\n",
    "                    continue\n",
    "                else:\n",
    "                    res = self.merge(res, link)\n",
    "        else:\n",
    "            l1 = lists[:len(lists)//2]\n",
    "            l2 = lists[len(lists)//2:]\n",
    "            m1 = self.func(l1)\n",
    "            m2 = self.func(l2)\n",
    "            res = self.merge(m1, m2)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def merge(self, p1, p2):\n",
    "        res = ListNode()\n",
    "        p = res\n",
    "        if p1 is None:\n",
    "            return p2\n",
    "        elif p2 is None:\n",
    "            return p1\n",
    "        while p1 is not None and p2 is not None:\n",
    "            if p1.val <= p2.val:\n",
    "                p.next = p1\n",
    "                p1 = p1.next\n",
    "            else:\n",
    "                p.next = p2\n",
    "                p2 = p2.next\n",
    "            p = p.next\n",
    "            if p1 is None:\n",
    "                p.next = p2\n",
    "            elif p2 is None:\n",
    "                p.next = p1\n",
    "        # print(\"merge!!!\",res.next)\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        stack=[]\n",
    "        for i in lists:\n",
    "            while i:\n",
    "                stack.append(i)\n",
    "                i=i.next\n",
    "        stack.sort(key=lambda x:x.val)\n",
    "        for i in range(len(stack)-1):\n",
    "            stack[i].next=stack[i+1]\n",
    "        if stack==[]:\n",
    "            return\n",
    "        return stack[0]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        interval = 1\n",
    "        n = len(lists)\n",
    "        while interval < n:\n",
    "            for i in range(0, n - interval, interval * 2):\n",
    "                lists[i] = self._merge(lists[i], lists[i + interval])\n",
    "            interval *= 2\n",
    "        return lists[0] if lists else None\n",
    "\n",
    "    def _merge(self, l1, l2):\n",
    "        dummy = l = ListNode(None)\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                l.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                l.next = l2\n",
    "                l2 = l2.next\n",
    "            l = l.next\n",
    "        l.next = l1 or l2\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "\n",
    "        head = ListNode(None)\n",
    "        start_node = head\n",
    "        while lists:\n",
    "            cur_min = None\n",
    "            min_node_index = None\n",
    "            index = 0\n",
    "            while index<len(lists):\n",
    "                if not lists[index]:\n",
    "                    lists.pop(index)\n",
    "                    continue\n",
    "                if (cur_min is None) or (cur_min>lists[index].val):\n",
    "                    cur_min = lists[index].val\n",
    "                    min_node_index = index\n",
    "                # print(start_node)\n",
    "                index +=1\n",
    "\n",
    "            if not lists:\n",
    "                break\n",
    "            start_node.next = lists.pop(min_node_index)\n",
    "            start_node = start_node.next\n",
    "            lists.append(start_node.next)\n",
    "\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "\n",
    "        def get_two_merge(list1, list2):\n",
    "            l1, l2, l = list1, list2, ListNode()\n",
    "            node = l\n",
    "\n",
    "            while l1 and l2:\n",
    "                if l1.val < l2.val:\n",
    "                    l.next = l1\n",
    "                    l1 = l1.next\n",
    "                else:\n",
    "                    l.next = l2\n",
    "                    l2 = l2.next\n",
    "                l = l.next\n",
    "\n",
    "            if l1:\n",
    "                l.next = l1\n",
    "            if l2:\n",
    "                l.next = l2\n",
    "            \n",
    "            return node.next\n",
    "        \n",
    "        n = len(lists)\n",
    "        if n == 0:\n",
    "            return ListNode().next\n",
    "        ans = lists[0]\n",
    "        for i in range(1, n):\n",
    "            another = lists[i]\n",
    "            ans = get_two_merge(ans, another)\n",
    "        return ans   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        head = ListNode()\n",
    "        cur = head\n",
    "        while True:\n",
    "            min_val = float('inf')\n",
    "            min_index = -1\n",
    "            for i in range(len(lists)):\n",
    "                if lists[i] and lists[i].val < min_val:\n",
    "                    min_val = lists[i].val\n",
    "                    min_index = i\n",
    "            if min_index == -1:\n",
    "                break\n",
    "            cur.next = lists[min_index]\n",
    "            cur = cur.next\n",
    "            lists[min_index] = lists[min_index].next\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        n = len(lists)\n",
    "        first_list = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if lists[i] != None and lists[i].val != None:\n",
    "                first_list += [(lists[i].val, i)]\n",
    "        heapify(first_list)\n",
    "         \n",
    "        result = ListNode()\n",
    "        ans = result\n",
    "        while len(first_list) > 0:\n",
    "            num, sequence = heappop(first_list)\n",
    "            lists[sequence] = lists[sequence].next\n",
    "            result.next = ListNode(num)\n",
    "            result = result.next\n",
    "\n",
    "            if lists[sequence] != None:\n",
    "                heappush(first_list, (lists[sequence].val, sequence))\n",
    "\n",
    "        return ans.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        #使用一个队列存储\n",
    "\n",
    "        heap=[]\n",
    "\n",
    "        for sub_list in lists:\n",
    "\n",
    "            while sub_list:\n",
    "\n",
    "                heap.append(sub_list.val)\n",
    "\n",
    "                sub_list=sub_list.next\n",
    "\n",
    "        #对heapify进行堆排序\n",
    "\n",
    "        import heapq\n",
    "\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        print(heap)\n",
    "\n",
    "        #heap.sort(reverse=True)\n",
    "\n",
    "        head=ListNode(None)\n",
    "\n",
    "        curr_list=head\n",
    "\n",
    "        while heap:\n",
    "\n",
    "            temp_list=ListNode(heapq.heappop(heap))\n",
    "\n",
    "            curr_list.next=temp_list\n",
    "\n",
    "            curr_list=curr_list.next\n",
    "\n",
    "        return head.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import heapq\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        heap = []\n",
    "        heapq.heapify(heap)\n",
    "        dumb = cur = ListNode()\n",
    "        for i, l in enumerate(lists):\n",
    "            if l:\n",
    "                heapq.heappush(heap, (l.val, i))\n",
    "        while heap:\n",
    "            val, i = heapq.heappop(heap)\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "            if lists[i].next:\n",
    "                lists[i] = lists[i].next\n",
    "                heapq.heappush(heap, (lists[i].val, i))\n",
    "        return dumb.next\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "\n",
    "        if not lists:return None\n",
    "\n",
    "        # 清理没有元素的链表\n",
    "        lists = [i for i in lists if i]\n",
    "\n",
    "        n  = len(lists)\n",
    "        if n == 0:return None\n",
    "\n",
    "        # 以头节点元素最小的链表为基准\n",
    "        # firstnodelist = [(i,i.val) for i in lists]\n",
    "        firstnodelist = [(i,lists[i].val) for i in range(n)]\n",
    "        minI , minV = min(firstnodelist , key = lambda x:x[1])\n",
    "\n",
    "        res = lists[minI]\n",
    "        lists.pop(minI)\n",
    "\n",
    "        pointer = res\n",
    "\n",
    "        while lists:\n",
    "\n",
    "            length = len(lists)\n",
    "\n",
    "            # 找到当前小于基准节点下一个节点的最小节点\n",
    "            firstnodelist = [(i,lists[i].val) for i in range(length)]\n",
    "            minI , minV = min(firstnodelist , key = lambda x:x[1])\n",
    "\n",
    "            # 当前基准节点有下一个节点\n",
    "            if pointer.next:\n",
    "\n",
    "                # 基准节点下一个的值大于选中的，执行插入\n",
    "                if minV < pointer.next.val:\n",
    "                    # 获取一个待插入节点的拷贝\n",
    "                    toInsert = lists[minI]\n",
    "                    lists[minI] = lists[minI].next\n",
    "                    toInsert.next =  pointer.next\n",
    "                    pointer.next = toInsert\n",
    "                    pointer = pointer.next\n",
    "\n",
    "                #下一个较小，不执行动作\n",
    "                else:\n",
    "                    pointer = pointer.next\n",
    "\n",
    "            # 当前基准节点没有下一个节点,直接插入\n",
    "            else:\n",
    "                 # 获取一个待插入节点的拷贝\n",
    "                toInsert = lists[minI]\n",
    "                lists[minI] = lists[minI].next\n",
    "                toInsert.next =  pointer.next\n",
    "                pointer.next = toInsert\n",
    "                pointer = pointer.next\n",
    "\n",
    "\n",
    "            # 清理没有元素的链表\n",
    "            lists = [i for i in lists if i]\n",
    "\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def have_traversed_all(self, listNodes):\n",
    "        for listNode in listNodes:\n",
    "            if listNode is not None:\n",
    "                return False \n",
    "        return True\n",
    "\n",
    "    def min_node(self, listNodes):\n",
    "        min_node = (float(\"inf\"), -1)\n",
    "        for i, listNode in enumerate(listNodes):\n",
    "            # return idx of the node with the smallest node \n",
    "            if listNode and listNode.val < min_node[0]:\n",
    "                min_node = (listNode.val, i)\n",
    "        return min_node[1]\n",
    "\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        # initialize a list of length k, with each element being the current node in each linked list that we are traversing to \n",
    "        curr_nodes = lists \n",
    "        start = ListNode()\n",
    "        curr = start\n",
    "        print(\"curr_nodes\", curr_nodes)\n",
    "        # while we haven't traversed through all the linked list:\n",
    "        while self.have_traversed_all(curr_nodes) == False:\n",
    "            # add the min of the k nodes to the returning linked list \n",
    "            min_node_idx = self.min_node(curr_nodes)\n",
    "            print(\"min_node_idx\", min_node_idx)\n",
    "            # update the node in the curr_nodes\n",
    "            curr.next = curr_nodes[min_node_idx]\n",
    "            curr = curr.next\n",
    "            curr_nodes[min_node_idx] = curr_nodes[min_node_idx].next\n",
    "            print(\"curr\", curr.val) \n",
    "        return start.next \n",
    "\n",
    "\"\"\"\n",
    "Optimizations:\n",
    "- For min_node, keep track of the min, and everytime we add to curr_nodes, we just compare with the min \n",
    "- \n",
    "\"\"\"\n",
    "\n",
    "# problems identified in the interview:\n",
    "# when there is a bug in the code, I don't understand my code, I need a way to quickly visualize what is happening and understand the bug \n",
    "# I need to practice doing print debugging \n",
    "\n",
    "# debugging strategies \n",
    "# always print \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        def merge(lists, left, right):\n",
    "            if not lists:\n",
    "                return \n",
    "            if left == right:\n",
    "                return lists[left]\n",
    "            if left > right:\n",
    "                return \n",
    "            mid = (left + right) //2 \n",
    "            return mergeSort(merge(lists, left, mid), merge(lists, mid+1, right))\n",
    "        def mergeSort(left, right):\n",
    "            cur = ListNode()\n",
    "            pre = cur \n",
    "            while left and right:\n",
    "                if left.val < right.val:\n",
    "                    new_node = ListNode(left.val)\n",
    "                    pre.next = new_node \n",
    "                    pre = pre.next \n",
    "                    left = left.next \n",
    "                else:\n",
    "                    new_node = ListNode(right.val)\n",
    "                    pre.next = new_node \n",
    "                    pre = pre.next \n",
    "                    right = right.next \n",
    "            if left:\n",
    "                pre.next = left \n",
    "            if right:\n",
    "                pre.next = right \n",
    "            return cur.next \n",
    "        return merge(lists, 0, len(lists)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        # while循环，两两分组归并\n",
    "        return self.merge_k_list(lists, 0, len(lists))\n",
    "    \n",
    "    def merge_k_list(self, lists, left, right):\n",
    "        if left == right:\n",
    "            return None\n",
    "        if left + 1 == right:\n",
    "            return lists[left]\n",
    "\n",
    "        mid = (left+right)//2\n",
    "        left_sort_result = self.merge_k_list(lists, left, mid)\n",
    "        right_sort_result = self.merge_k_list(lists, mid, right)\n",
    "\n",
    "        return self.merge(left_sort_result, right_sort_result)\n",
    "    \n",
    "    def merge(self, left, right):\n",
    "        dummy_head = ListNode(0, None)\n",
    "        c_node = dummy_head\n",
    "\n",
    "        while(left is not None and right is not None):\n",
    "            if left.val < right.val:\n",
    "                c_node.next = ListNode(left.val, None)\n",
    "                left = left.next\n",
    "            else:\n",
    "                c_node.next = ListNode(right.val, None)\n",
    "                right = right.next\n",
    "            c_node = c_node.next\n",
    "        \n",
    "        if left is not None:\n",
    "            c_node.next = left\n",
    "        if right is not None:\n",
    "            c_node.next = right\n",
    "        \n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class NodeIter:\n",
    "    def __init__(self,head):\n",
    "        self.p=ListNode(next=head)\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "    def __next__(self):\n",
    "        self.p=self.p.next\n",
    "        if not self.p:\n",
    "            raise StopIteration\n",
    "        return self.p\n",
    "class Solution:\n",
    "    import heapq\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        ll=[]\n",
    "        for li in lists:\n",
    "            ll.append(NodeIter(li))\n",
    "        it=heapq.merge(*ll, key=attrgetter('val'))\n",
    "        h=ListNode()\n",
    "        last=h\n",
    "        for i in it:\n",
    "            last.next=i\n",
    "            last=i\n",
    "        last.net=None\n",
    "        return h.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "      \"\"\"\n",
    "      1. 小顶堆\n",
    "      \"\"\"\n",
    "      # if not lists:\n",
    "      #   return lists\n",
    "      \n",
    "      from heapq import heappush, heappop\n",
    "      hq = []\n",
    "      dic = {}\n",
    "      \n",
    "      # initialize heap\n",
    "      for i, link in enumerate(lists):\n",
    "        if not link:\n",
    "          continue\n",
    "        print(i, link)\n",
    "        dic[f\"{i}_0\"] = link\n",
    "        heappush(hq, [link.val, f\"{i}_0\"])\n",
    "      # print(dic)\n",
    "\n",
    "      thead = ListNode()\n",
    "      head = thead\n",
    "      while hq:\n",
    "        [cur_min_val, position] = heappop(hq)\n",
    "        # create node\n",
    "        temp = ListNode(cur_min_val)\n",
    "        head.next = temp\n",
    "        head = head.next\n",
    "\n",
    "        if dic[position].next:\n",
    "          next_index = f\"{position.split('_')[0]}_{int(position.split('_')[1])+1}\"\n",
    "          dic[next_index] = dic[position].next\n",
    "          heappush(hq, [dic[position].next.val, next_index])\n",
    "\n",
    "      return thead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class SkipListNode: \n",
    "\n",
    "\tdef __init__(self): \n",
    "\t\tself.prev = None \n",
    "\t\tself.next = None \n",
    "\t\tself.index = None \n",
    "\t\tself.up = None\n",
    "\t\tself.pv = None \n",
    "\t\n",
    "class SkipList: \n",
    "\n",
    "\tdef __init__(self): \n",
    "\t\tself.__multiple = True\n",
    "\t\tself.__reset() \n",
    "\n",
    "\tdef __reset(self): \n",
    "\t\tself.__size = 0 \n",
    "\t\tself.__head_node_list = [] \n",
    "\t\tself.__tail_node_list = [] \n",
    "\t\tnode = SkipListNode() \n",
    "\t\tself.__head_node_list.append(node) \n",
    "\t\tself.__tail_node_list.append(node) \n",
    "\n",
    "\tdef __need_add(self): \n",
    "\t\treturn 0 == random.randint(0, 3) \n",
    "\n",
    "\tdef clear(self): \n",
    "\t\tself.__reset()\n",
    "\n",
    "\tdef __insert_node(self, prev, pv, deep):\n",
    "\t\tnode = SkipListNode()\n",
    "\t\tnode.pv = pv\n",
    "\t\tif None != prev.next:\n",
    "\t\t\tprev.next.prev = node\n",
    "\t\t\tnode.next = prev.next\n",
    "\t\telse:\n",
    "\t\t\tself.__tail_node_list[deep] = node\n",
    "\t\tprev.next = node\n",
    "\t\tnode.prev = prev\n",
    "\t\treturn node\n",
    "\n",
    "\tdef __insert_deep(self, prev, deep, pv):\n",
    "\t\t#for node=prev; None!=node; node=node.next:\n",
    "\t\tnode = prev\n",
    "\t\twhile None != node:\n",
    "\t\t\tif not self.__multiple and None != node.next and pv == node.next.pv:\n",
    "\t\t\t\treturn None\n",
    "\t\t\tif None == node.next or pv < node.next.pv:\n",
    "\t\t\t\tif deep > 0:\n",
    "\t\t\t\t\taddnode = self.__insert_deep(node.index, deep - 1, pv)\n",
    "\t\t\t\t\tindexnode = None\n",
    "\t\t\t\t\tif None != addnode and self.__need_add():\n",
    "\t\t\t\t\t\tindexnode = self.__insert_node(node, pv, deep)\n",
    "\t\t\t\t\t\tindexnode.index = addnode\n",
    "\t\t\t\t\t\taddnode.up = indexnode\n",
    "\t\t\t\t\treturn indexnode\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\taddnode = self.__insert_node(node, pv, deep)\n",
    "\t\t\t\t\tif None != addnode:\n",
    "\t\t\t\t\t\tself.__size = self.__size + 1\n",
    "\t\t\t\t\treturn addnode\n",
    "\t\t\tnode = node.next\n",
    "\t\treturn None\n",
    "\t\n",
    "\tdef insert(self, pv):\n",
    "\t\taddnode = self.__insert_deep(self.__head_node_list[len(self.__head_node_list) - 1],\n",
    "\t\t\t\t\t\t\t\t\t\tlen(self.__head_node_list) - 1, pv)\n",
    "\t\tif None != addnode and self.__need_add() and len(self.__head_node_list) < 32:\n",
    "\t\t\theadnode = SkipListNode()\n",
    "\t\t\theadnode.index = self.__head_node_list[len(self.__head_node_list)-1]\n",
    "\t\t\tself.__head_node_list[len(self.__head_node_list)-1].up = headnode\n",
    "\t\t\tself.__head_node_list.append(headnode)\n",
    "\t\t\tself.__tail_node_list.append(headnode)\n",
    "\t\t\tindexnode = self.__insert_node(headnode, pv, len(self.__head_node_list)-1)\n",
    "\t\t\tindexnode.index = addnode\n",
    "\t\t\taddnode.up = indexnode\n",
    "\t\t\t#addnode = indexnode\n",
    "\t\n",
    "\tdef __find_deep(self, prev, pv):\n",
    "\t\tnode = prev\n",
    "\t\twhile None != node:\n",
    "\t\t\tif None != node.prev and pv == node.pv:\n",
    "\t\t\t\tindexnode = node\n",
    "\t\t\t\twhile None != indexnode.index:\n",
    "\t\t\t\t\tindexnode = indexnode.index\n",
    "\t\t\t\treturn indexnode\n",
    "\t\t\tif None == node.next or pv < node.next.pv:\n",
    "\t\t\t\treturn self.__find_deep(node.index, pv)\n",
    "\t\t\tnode = node.next\n",
    "\t\treturn None\n",
    "\t\n",
    "\tdef find(self, pv):\n",
    "\t\treturn self.__find_deep(self.__head_node_list[len(self.__head_node_list) - 1], pv)\n",
    "\n",
    "\tdef __erase_deep(self, prev, deep, pv):\n",
    "\t\tnode = prev\n",
    "\t\twhile None != node:\n",
    "\t\t\tif None != node.prev and pv == node.pv:\n",
    "\t\t\t\tindexnode = node\n",
    "\t\t\t\twhile None != indexnode:\n",
    "\t\t\t\t\tindexnode.prev.next = indexnode.next\n",
    "\t\t\t\t\tif None != indexnode.next:\n",
    "\t\t\t\t\t\tindexnode.next.prev = indexnode.prev\n",
    "\t\t\t\t\telse:\n",
    "\t\t\t\t\t\tself.__tail_node_list[deep] = indexnode.prev\n",
    "\t\t\t\t\tindexnode = indexnode.index\n",
    "\t\t\t\t\tdeep = deep - 1\n",
    "\t\t\t\tself.__size = self.__size - 1\n",
    "\t\t\t\treturn True\n",
    "\t\t\tif None == node.next or pv < node.next.pv:\n",
    "\t\t\t\tif deep > 0:\n",
    "\t\t\t\t\treturn self.__erase_deep(node.index, deep - 1, pv)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\tnode = node.next\n",
    "\t\treturn False\n",
    "\n",
    "\tdef erase(self, pv):\n",
    "\t\treturn self.__erase_deep(self.__head_node_list[len(self.__head_node_list) - 1], len(self.__head_node_list) - 1, pv)\n",
    "\t\n",
    "\tdef erase_node(self, node):\n",
    "\t\tif None != node.index:\n",
    "\t\t\treturn False\n",
    "\t\tdeep = 0\n",
    "\t\twhile None != node:\n",
    "\t\t\tnode.prev.next = node.next\n",
    "\t\t\tif None != node.next:\n",
    "\t\t\t\tnode.next.prev = node.prev\n",
    "\t\t\telse:\n",
    "\t\t\t\tself.__tail_node_list[deep] = node.prev\n",
    "\t\t\tnode = node.up\n",
    "\t\t\tdeep = deep + 1\n",
    "\t\tself.__size = self.__size - 1\n",
    "\t\treturn True\n",
    "\n",
    "\tdef size(self):\n",
    "\t\treturn self.__size\n",
    "\n",
    "\tdef begin(self):\n",
    "\t\treturn self.__head_node_list[0].next\n",
    "\n",
    "\tdef rbegin(self):\n",
    "\t\treturn self.__tail_node_list[0]\n",
    "\n",
    "\tdef max_deep(self):\n",
    "\t\treturn len(self.__head_node_list)\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class HeadNode:\n",
    "\tdef __init__(self, val, index):\n",
    "\t\tself.val = val\n",
    "\t\tself.index = index\n",
    "\tdef __lt__(self, o):\n",
    "\t\treturn self.val < o.val\n",
    "\tdef __eq__(self, o):\n",
    "\t\treturn self.val == o.val\n",
    "\n",
    "class Solution:\n",
    "\tdef mergeKLists(self, lists):\n",
    "\t\tl = SkipList()\n",
    "\t\tfor i in range(len(lists)):\n",
    "\t\t\tif None != lists[i]:\n",
    "\t\t\t\tnode = HeadNode(lists[i].val, i)\n",
    "\t\t\t\tl.insert(node)\n",
    "\t\thead = None\n",
    "\t\ttail = None\n",
    "\t\twhile l.size() > 0:\n",
    "\t\t\tnode = l.begin()\n",
    "\t\t\tcurnode = lists[node.pv.index]\n",
    "\t\t\tlists[node.pv.index] = lists[node.pv.index].next\n",
    "\t\t\tif lists[node.pv.index]:\n",
    "\t\t\t\tnewnode = HeadNode(lists[node.pv.index].val, node.pv.index)\n",
    "\t\t\t\tl.insert(newnode)\n",
    "\t\t\tl.erase_node(node)\n",
    "\t\t\tcurnode.next = None\n",
    "\t\t\tif None != tail:\n",
    "\t\t\t\ttail.next = curnode\n",
    "\t\t\telse:\n",
    "\t\t\t\thead = curnode\n",
    "\t\t\ttail = curnode\n",
    "\t\treturn head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        import copy\n",
    "        if not lists:\n",
    "            return None\n",
    "        result = None\n",
    "        tail_node = None\n",
    "        while True:\n",
    "            lists =[node for node in filter(lambda x: x, lists)]\n",
    "            if not lists:\n",
    "                break\n",
    "            min_node_index = 0\n",
    "            for index in range(1, len(lists)):\n",
    "                if lists[min_node_index].val > lists[index].val:\n",
    "                    min_node_index = index\n",
    "            if result is None:\n",
    "                result = copy.deepcopy(lists[min_node_index])\n",
    "                tail_node = result\n",
    "            else:\n",
    "                tail_node.next = copy.deepcopy(lists[min_node_index])\n",
    "                tail_node = tail_node.next\n",
    "            tail_node.next = None\n",
    "            min_node = lists[min_node_index]\n",
    "            lists[min_node_index] = None if min_node.next is None else min_node.next\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        def merge2Lists(a: ListNode, b: ListNode):\n",
    "            if a == None:\n",
    "                return b\n",
    "            if b == None:\n",
    "                return a\n",
    "            \n",
    "            a, b = (a, b) if a.val < b.val else (b, a)\n",
    "            a.next = merge2Lists(a.next, b)\n",
    "            return a\n",
    "\n",
    "        def dividMerge(lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "            if len(lists) < 1:\n",
    "                return None\n",
    "            elif len(lists) == 1:\n",
    "                return lists[0]\n",
    "\n",
    "            mid = len(lists) // 2\n",
    "            return merge2Lists(dividMerge(lists[:mid]), dividMerge(lists[mid:]))\n",
    "\n",
    "        def countNode(head: ListNode) -> int:\n",
    "            count = 0\n",
    "            while head != None:\n",
    "                head = head.next\n",
    "                count = count + 1\n",
    "            return count\n",
    "        \n",
    "        arr = [x for x in lists if x != None]\n",
    "        arr.sort(key=lambda x: x.val)\n",
    "\n",
    "        return dividMerge(arr)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        def merge2Lists(a: ListNode, b: ListNode):\n",
    "            if a == None:\n",
    "                return b\n",
    "            if b == None:\n",
    "                return a\n",
    "            \n",
    "            a, b = (a, b) if a.val < b.val else (b, a)\n",
    "            a.next = merge2Lists(a.next, b)\n",
    "            return a\n",
    "\n",
    "        def dividMerge(lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "            if len(lists) < 1:\n",
    "                return None\n",
    "            elif len(lists) == 1:\n",
    "                return lists[0]\n",
    "\n",
    "            mid = len(lists) // 2\n",
    "            return merge2Lists(dividMerge(lists[:mid]), dividMerge(lists[mid:]))\n",
    "\n",
    "        \n",
    "        arr = [x for x in lists if x != None]\n",
    "        arr.sort(key=lambda x: x.val)\n",
    "\n",
    "        return dividMerge(arr)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def merge2lists(self, node1, node2):\n",
    "        if node1 == None:\n",
    "            return node2\n",
    "        if node2 == None:\n",
    "            return node1\n",
    "        res = tmp = ListNode(0)\n",
    "        while node1 and node2:\n",
    "            if node1.val < node2.val:\n",
    "                tmp.next = node1\n",
    "                node1 = node1.next\n",
    "            else:\n",
    "                tmp.next = node2\n",
    "                node2 = node2.next\n",
    "            tmp = tmp.next\n",
    "        if node1:\n",
    "            tmp.next = node1\n",
    "        if node2:\n",
    "            tmp.next = node2\n",
    "        return res.next\n",
    "    def fenzhimerge(self, lists, left, right):\n",
    "        if left > right:\n",
    "            return None\n",
    "        if left == right:\n",
    "            return lists[left]\n",
    "        return self.merge2lists(self.merge2lists(lists[left],lists[right]), self.fenzhimerge(lists,left+1,right-1))\n",
    "        \n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        left = 0\n",
    "        right = len(lists) - 1\n",
    "        return self.fenzhimerge(lists,left,right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def quicksort(list):\n",
    "    if len(list)<2:\n",
    "        return list\n",
    "    pivot = list[0]\n",
    "    newlist = list[1:]\n",
    "    greater = [i for i in newlist if i.val <= pivot.val]\n",
    "    upper = [i for i in newlist if i.val > pivot.val]\n",
    "    return quicksort(greater)+[pivot]+quicksort(upper)\n",
    "def change_next(list):\n",
    "    for i in range(0,len(list)-1):\n",
    "        list[i].next = list[i+1]\n",
    "    list[-1].next = None\n",
    "    return list[0]\n",
    "class Solution:\n",
    "    \n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        if len(lists)==0:\n",
    "            return \n",
    "    \n",
    "        newL = []\n",
    "        for i in lists:\n",
    "            thisnode = i\n",
    "            \n",
    "            while thisnode != None:\n",
    "            \n",
    "                newL.append(thisnode)\n",
    "                thisnode = thisnode.next\n",
    "     \n",
    "        finallist = quicksort(newL)\n",
    "        if len(finallist)==0:\n",
    "            return\n",
    "        finallist = change_next(finallist)\n",
    "        return finallist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        heads = copy.deepcopy(lists)\n",
    "        def end_ls(x):\n",
    "            for i in x:\n",
    "                if i is not None:\n",
    "                    return True\n",
    "            return False\n",
    "        dum = None\n",
    "        p = None\n",
    "        while end_ls(heads):\n",
    "            m = 1e9\n",
    "            h = None\n",
    "            for i in range(len(heads)):\n",
    "                if heads[i] is not None and heads[i].val < m:\n",
    "                    h = i\n",
    "                    m = heads[i].val\n",
    "            heads[h] = heads[h].next\n",
    "            # p.val = m\n",
    "            if p is None:\n",
    "                p = ListNode()\n",
    "                dum = p\n",
    "            else:\n",
    "                p.next = ListNode()\n",
    "                p = p.next\n",
    "            p.val = m\n",
    "            # p = p.next\n",
    "        \n",
    "\n",
    "        return dum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "# ListNode.__lt__ = lambda a,b: a.val<b.val\n",
    "ListNode.__lt__ = lambda a,b:a.val <b.val\n",
    "from heapq import heappush,heappop,heapify\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        listnums = []\n",
    "        for alist in lists:\n",
    "            arr = deque()\n",
    "            while alist:\n",
    "                arr.append(alist.val)\n",
    "                alist=alist.next\n",
    "            listnums.append(arr)\n",
    "        heapify(listnums)\n",
    "\n",
    "        res = []\n",
    "        while len(listnums)>0:\n",
    "            arr = heappop(listnums)\n",
    "            if len(arr)>0:\n",
    "                res.append(arr.popleft())\n",
    "                heappush(listnums,arr)\n",
    "\n",
    "        # pre = ListNode()\n",
    "        nodes = [ListNode(val) for val in res]\n",
    "        # print(nodes)\n",
    "        for i in range(len(nodes)-1):\n",
    "            nodes[i].next = nodes[i+1]\n",
    "        # print(len(nodes))\n",
    "        return nodes[0] if len(nodes)>0 else None\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # res=None\n",
    "        # h = [head for head in lists if head]\n",
    "        # # print(h)\n",
    "        # heapify(h)\n",
    "        # # print(h)\n",
    "        # res=cur = ListNode()\n",
    "        # while h:\n",
    "        #     node = heappop(h)\n",
    "        #     if node.next:\n",
    "        #         heappush(h,node.next)\n",
    "        #     cur.next = node\n",
    "        #     cur = cur.next\n",
    "\n",
    "        # return res.next\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def iter_linked_list(self, node: Optional[ListNode]):\n",
    "        while node is not None:\n",
    "            yield node.val\n",
    "            node = node.next\n",
    "    \n",
    "    def linked_list_from_iterable(self, iterable):\n",
    "        it = iter(iterable)\n",
    "        try:\n",
    "            head = ListNode(next(it))\n",
    "        except StopIteration:\n",
    "            return None\n",
    "        \n",
    "        tail = head\n",
    "        for item in it:\n",
    "            tail.next = ListNode(item)\n",
    "            tail = tail.next\n",
    "        \n",
    "        return head\n",
    "\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        return self.linked_list_from_iterable(\n",
    "            heapq.merge(*map(self.iter_linked_list, lists))\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def toNode(a) -> ListNode:\n",
    "    head, tail = None, None\n",
    "    for val in a:\n",
    "        if not head:\n",
    "            head = tail = ListNode(val)\n",
    "        else:\n",
    "            tail.next = ListNode(val)\n",
    "            tail = tail.next\n",
    "    return head\n",
    "\n",
    "def toList(head: ListNode | None):\n",
    "    cur = head\n",
    "    while cur:\n",
    "        yield cur.val\n",
    "        cur = cur.next\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        if not lists or all(not li for li in lists):\n",
    "            return None\n",
    "        iterList = [toList(nd) for nd in lists]\n",
    "        li = heapq.merge(*iterList)\n",
    "        return toNode(li)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def merge_2_linked_lists(self, l1, l2):\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        if l2 is None:\n",
    "            return l1\n",
    "        if l1.val > l2.val:\n",
    "            l2.next = self.merge_2_linked_lists(l1, l2.next)\n",
    "            return l2\n",
    "        else:\n",
    "            l1.next = self.merge_2_linked_lists(l2, l1.next)\n",
    "            return l1\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        ans = None\n",
    "        for linked in lists:\n",
    "            ans = self.merge_2_linked_lists(ans, linked)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        if lists is None:\n",
    "            return None\n",
    "        n = len(lists)\n",
    "        new_lists = []\n",
    "        for i in range(n):\n",
    "            if lists[i] is not None:\n",
    "                new_lists.append(lists[i])\n",
    "            else:\n",
    "                continue\n",
    "        lists = copy.deepcopy(new_lists)\n",
    "        fake_head = ListNode(val=0, next=None)\n",
    "        p = fake_head\n",
    "        num_list = []\n",
    "        n = len(lists)\n",
    "        flags = n\n",
    "        for i in range(n):\n",
    "            num_list.append(lists[i].val)\n",
    "        while flags > 0:\n",
    "            target_index = self.get_min_index(num_list)\n",
    "            p.next = lists[target_index]\n",
    "            p = p.next\n",
    "            lists[target_index] = lists[target_index].next\n",
    "            if lists[target_index] is None:\n",
    "                num_list[target_index] = 999999\n",
    "                flags -= 1\n",
    "            else:\n",
    "                num_list[target_index] = lists[target_index].val\n",
    "        return fake_head.next\n",
    "\n",
    "    def get_min_index(self, nums):\n",
    "        min_value = min(nums)\n",
    "        min_index = nums.index(min_value)\n",
    "        return min_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# 暴力：时间复杂度O(NK)\n",
    "# 优化：时间复杂度O(NlogK) 维护一个小根堆（优先队列）\n",
    "# class Solution:\n",
    "#     def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "#         # print(len(lists))\n",
    "#         import heapq\n",
    "#         dummy = ListNode(0)\n",
    "#         res = dummy\n",
    "#         k = len(lists)\n",
    "#         head = []\n",
    "#         for i in range(k):\n",
    "#             if lists[i]:\n",
    "#                 heapq.heappush(head,(lists[i].val,i))\n",
    "#                 lists[i] = lists[i].next\n",
    "#         # print(head)\n",
    "#         while head:\n",
    "#             val, i = heapq.heappop(head)\n",
    "#             # print(head)\n",
    "#             res.next = ListNode(val)\n",
    "#             res = res.next\n",
    "#             if lists[i]:\n",
    "#                 heapq.heappush(head,(lists[i].val,i))\n",
    "#                 lists[i] = lists[i].next\n",
    "#         return dummy.next\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        if len(lists)==0:\n",
    "            return None\n",
    "        l = 0\n",
    "        r = len(lists)-1\n",
    "        return self.merge_sort(l,r,lists)\n",
    "\n",
    "    def merge_sort(self, l,r,lists):\n",
    "\n",
    "        if l==r:\n",
    "            return lists[l]\n",
    "        \n",
    "        mid = (l+r)//2\n",
    "        l1 = self.merge_sort(l,mid,lists)\n",
    "        l2 = self.merge_sort(mid+1,r,lists)\n",
    "\n",
    "        return self.merge_two(l1,l2)\n",
    "\n",
    "    def merge_two(self,l1,l2):\n",
    "        if not l1: return l2\n",
    "        if not l2: return l1\n",
    "        if l1.val <= l2.val:\n",
    "            l1.next = self.merge_two(l1.next,l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.merge_two(l1,l2.next)\n",
    "            return l2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        if len(lists) == 0:\n",
    "            return\n",
    "        if len(lists) == 1:\n",
    "            return lists[0]\n",
    "        def merge(l1, l2):\n",
    "            if l1 is None:\n",
    "                return l2\n",
    "            if l2 is None:\n",
    "                return l1\n",
    "            if l1.val < l2.val:\n",
    "                l1.next = merge(l1.next, l2)\n",
    "                return l1       \n",
    "            else:\n",
    "                l2.next = merge(l2.next, l1)\n",
    "                return l2 \n",
    "        node = merge(lists[0],lists[1])\n",
    "        for i in range(2,len(lists)):\n",
    "            node = merge(node,lists[i])\n",
    "        return node\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        def cap(l1,l2):\n",
    "            if not l1:\n",
    "                return l2\n",
    "            if not l2:\n",
    "                return l1\n",
    "            if l1.val>l2.val:\n",
    "                l2.next = cap(l1,l2.next)\n",
    "                return l2\n",
    "            else:\n",
    "                l1.next = cap(l1.next,l2)\n",
    "                return l1\n",
    "        if len(lists)==0:\n",
    "            return None\n",
    "        res = None\n",
    "        for i in lists:\n",
    "            res = cap(res,i)\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def merge2Lists(self,list1:Optional[ListNode],list2:Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not list1:\n",
    "            return list2\n",
    "        elif not list2:\n",
    "            return list1\n",
    "        elif list1.val < list2.val:\n",
    "            list1.next = self.merge2Lists(list1.next,list2)\n",
    "            return list1\n",
    "        else:\n",
    "            list2.next = self.merge2Lists(list2.next,list1)\n",
    "            return list2\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        left  = 0\n",
    "        right = len(lists)\n",
    "        mid = (left + right)// 2\n",
    "        if right == 0:\n",
    "            return None\n",
    "        if right == 1:\n",
    "            return lists[0]\n",
    "        left_list = self.mergeKLists(lists[left:mid])\n",
    "        right_list = self.mergeKLists(lists[mid:right])\n",
    "        return self.merge2Lists(left_list,right_list)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
